package com.mg;

import java.io.Serializable;
import java.util.*;
import java.util.concurrent.locks.ReentrantLock;
import java.util.function.Consumer;

/**
 * 可并发写动态集合，增删改操作，需要上锁，该集合对于读操作的效率比较高；对写操作，由于加锁解锁的操作，会导致效率不高<br/>
 * 补充：<br/>
 *  1：CopyOnWriteArrayList用复制操作耗费高昂的内存和计算资源为代价，换来的是读读不互斥，读写不互斥，适用于读多写极少的场景下，比如黑名单、配置属性等等。<br/>
 *  2：CopyOnWriteArrayList只能保证最终一致性，不能保证实时一致性。因为读写是在两个容器进行的，只有当写操作执行完毕引入指向新容器后，读才能感知到容器的变化。
 * @author fiver
 * @param <E>
 */
public class MyCopyOnWriteArrayList<E> implements List<E>, RandomAccess, Cloneable, Serializable {

    /**
     * 修改集合时上锁
     */
    final transient ReentrantLock lock = new ReentrantLock();

    /**
     * 正真存储元素的地方，只允许通过getArray和setArray访问
     */
    private transient volatile  Object[] array;


    /**
     * 三种初始化方式：无参
     */
    public MyCopyOnWriteArrayList() {
        Object[] objects = new Object[0];
        setArray(objects);
    }

    /**
     * 三种初始化方式：数组的方式
     */
    public MyCopyOnWriteArrayList(E[] toCopyIn) {
        setArray(Arrays.copyOf(toCopyIn, toCopyIn.length, Object[].class));
    }

    /**
     * 三种初始化方式：集合的方式
     */
    public MyCopyOnWriteArrayList(Collection<? extends E> c) {
        Object[] elements;

        if (c.getClass() == MyCopyOnWriteArrayList.class) {
            elements = ((MyCopyOnWriteArrayList<?>)c).getArray();
        } else {
            // 需要注意的是, c.toArray()返回的不一定是Object[]类型
            elements = c.toArray();
            if (elements.getClass() != Object[].class) {
                Arrays.copyOf(elements, elements.length, Object[].class);
            }
        }
        setArray(c.toArray(elements));
    }


    final Object[] getArray() {
        return array;
    }

    final void setArray(Object[] array) {
        this.array = array;
    }


    @Override
    public boolean add(E e) {
        final ReentrantLock lock = this.lock;
        lock.lock();
        try {
            Object[] elements  = getArray();
            int len = elements.length;

            //相当于对元数组扩容
            Object[] newElements = Arrays.copyOf(elements, len + 1);

            //插入新元素到数组的末尾
            newElements[len] = e;

            //再设置回去
            setArray(newElements);
            return true;
        } finally {
            lock.unlock();
        }
    }


    @Override
    public void add(int index, E e) {
        final ReentrantLock lock = this.lock;
        // 1、加锁
        lock.lock();
        try {
            // 2、拷贝一份旧数组，从而不会影响到读功能（因此对读操作来说, 会出现弱一致性问题）
            Object[] element = getArray();

            int len = element.length;

            // 3、 检查是否越界, 正常范围是 [0, len]
            if (index > len || index < 0) {
                throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + len);
            }

            // 临时的、用来进行添加操作的数组
            Object[] newElements;

            // 在拷贝过程中需要移动的元素长度, 如果长度为0，说明添加的位置就是末尾位置, 否则就需要分成两段来分别移动了
            int moved = len - index;

            // 4、区分插入的位置是不是末尾, 如果插入的位置就是原数组的末尾
            if (moved == 0) {
                newElements = Arrays.copyOf(element, len + 1);
            } else {
                newElements = new Object[len + 1];
                System.arraycopy(element, 0, newElements, 0, index);
                System.arraycopy(element, index, newElements, index + 1, moved);
            }

            // 5、在指定位置插入新元素
            newElements[index] = e;
            // 6、将新的元素重新设置给全局属性, 保证最终一致性
            setArray(newElements);
        } finally {
            // 7、释放锁
            lock.unlock();
        }
    }

    @Override
    public void forEach(Consumer<? super E> action) {
        if (action == null) {
            throw new NullPointerException();
        }
        Object[] elements = getArray();
        int len = elements.length;
        for (int i = 0; i < len; ++i) {
            @SuppressWarnings("unchecked")
            E e = (E) elements[i];
            action.accept(e);
        }
    }

    @Override
    public boolean addAll(Collection<? extends E> c) {
        return false;
    }


    @Override
    public boolean addAll(int index, Collection<? extends E> c) {
        return false;
    }

    /**
     * CopyOnWriteArrayList集合独有的方法,如果该元素不存在于集合中, 才进行添加, 返回true; 否则, 返回false
     * @param e
     * @return
     */
    public boolean addIfAbsent(E e) {
        Object[] array = getArray();
        //已经存在了, 直接返回false
        if (indexOf(e, array, 0, array.length) >= 0) {
            return false;
        } else {
            return addIfAbsent(e, array);
        }
    }

    /**
     * 需要对照传入的快照，若不一致，需要进行对比; 若满足条件，则扩容后，再将元素添加到末尾，并返回true
     * @param e
     * @param snapshot
     * @return
     */
    private boolean addIfAbsent(E e, Object[] snapshot) {
        final ReentrantLock lock = this.lock;
        lock.lock();
        try {
            Object[] current = getArray();
            int len = current.length;

            if (snapshot != current) {
                int minLen = Math.min(snapshot.length, len);
                for (int i = 0; i < minLen; i++) {
                    //中间的某个值被修改，并且被
                    if (snapshot[i] != current[i] && e == current[i]) {
                        return false;
                    }
                }

                if (indexOf(e, current, 0, current.length) >= 0) {
                    return false;
                }
            }

            Object[] newArray = Arrays.copyOf(current, len + 1);
            newArray[len] = e;
            setArray(newArray);
            return true;
        } finally {
            lock.unlock();
        }
    }


    @Override
    public boolean contains(Object o) {
        Object[] elements = getArray();
        return indexOf(o, elements, 0, elements.length) >= 0;
    }


    /**
     * 查找指定值o，在数组elements中的索引值，对数组查找的范围为[index, fence], 左闭右开, 注意需要区分o是否为null
     * @param o         待查找元素
     * @param elements  被查找的数组
     * @param index     数组的起始位置
     * @param fence     数组的结束位置（开区间）
     * @return          返回值-1表示不包含指定元素，否则返回对应的索引位置
     */
    private static int indexOf(Object o, Object[] elements, int index, int fence) {
        if (o == null) {
            for (int i = index; i < fence; i++) {
                if (elements[i] == null) {
                    return i;
                }
            }
        } else {
            for (int i = index; i < fence; i++) {
                if (o.equals(elements[i])) {
                    return i;
                }
            }
        }
        return -1;
    }


    @Override
    public int size() {
        return getArray().length;
    }


    @Override
    public E remove(int index) {
        Object[] array = getArray();

        E oldValue = array(index);

        int len = array.length;

        int numMoved = len - 1 - index;

        //说明删除的是数组的末尾位置上的元素
        if (numMoved == 0) {
//            Object src,  int  srcPos, Object dest, int destPos, int length);
            setArray(Arrays.copyOf(array, len - 1));
        } else {
            Object[] newArray = new Object[len - 1];
            System.arraycopy(array, 0, newArray, 0, len - 1);
            System.arraycopy(array, index + 1, newArray, index, numMoved);
            setArray(newArray);
        }
        return oldValue;
    }

    @Override
    public boolean isEmpty() {
        return size() == 0;
    }


    @Override
    public Iterator<E> iterator() {
        return null;
    }


    @Override
    public Object[] toArray() {
        return new Object[0];
    }

    @Override
    public <T> T[] toArray(T[] a) {
        return null;
    }


    @Override
    public boolean remove(Object o) {
        return false;
    }


    @Override
    public boolean containsAll(Collection<?> c) {
        return false;
    }

    @Override
    public boolean removeAll(Collection<?> c) {
        return false;
    }

    @Override
    public boolean retainAll(Collection<?> c) {
        return false;
    }

    @Override
    public void clear() {

    }

    @Override
    public E get(int index) {
        return array(index);
    }

    E array(int index) {
        return (E) getArray()[index];
    }

    @Override
    public E set(int index, E element) {
        return null;
    }

    @Override
    public int indexOf(Object o) {
        return 0;
    }

    @Override
    public int lastIndexOf(Object o) {
        return 0;
    }

    @Override
    public ListIterator<E> listIterator() {
        return null;
    }

    @Override
    public ListIterator<E> listIterator(int index) {
        return null;
    }

    @Override
    public List<E> subList(int fromIndex, int toIndex) {
        return null;
    }
}